package com.kehao.newcoder;


import java.util.ArrayList;
import java.util.Collections;

public class NC37Solution {


    public class Interval {
        int start;
        int end;
        Interval() {
            start = 0;
            end = 0;
        }
        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }


    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals==null||intervals.isEmpty()){
            return intervals;
        }
        ArrayList<Interval> result = new ArrayList<>();
        result.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            result.add(intervals.get(i));
            for (int j = 0; j < result.size()-1; j++) {
                Interval last = result.get(result.size()-1);
                Interval t = result.get(j);
                if((t.start<=last.start&&t.end>=last.start)||(last.start<t.start&&last.end>= t.start)){
                    result.remove(result.size()-1);
                    result.remove(j);
                    result.add(new Interval(Math.min(t.start,last.start),Math.max(t.end,last.end)));
                    j--;
                }
            }
        }
        Collections.sort(result,(i1,i2)->i1.start-i2.start);
        return result;
    }
}
